The present invention relates to element placement optimization method and apparatus for determining an optimal placement of constituent elements such as LSIs. More particularly, the present invention is concerned with an element placement optimizing method and apparatus suited profitably for determining efficiently an optimal placement of the LSI constituent elements or the like within a reduced time as well as a method and apparatus for making decision as to the optimal placement.
In integrated circuits such as LSIs and others, a plurality of individual elements disposed on a chip are mutually interconnected by wiring conductors or lines. In this connection, it is noted that the overall line length in a LSI becomes significantly different when the positions of constituent elements placed in a matrix array, for example, are exchanged. Accordingly, for designing the integrated circuits, there is a need for optimizing the placement of the individual constituent elements so that the wiring length is shortened as far as practically possible. This in return reduces the cost involved in the manufacture of the integrated circuits. There have been developed a variety of design automation techniques for determining the optimal element placement for LSIs and others with the aid of a computer.
FIG. 13 of the accompanying drawings shows a flow chart for illustrating a related art element placement optimizing method which is sometimes referred to as the repetitive improvement method. This known repetitive improvement method is carried out by a sequential processing type computer known. Referring to FIG. 13, the number N represents the number of times a placement improving operation is to be repeatedly executed and is set at step 21. The setting of initial locations for individual elements by using pseudo-random numbers is set at step 22. Next, two paired element candidates are selected randomly by using pseudo-random numbers at step 23. Then it is arithmetically determined to what extent the cost could be reduced on the assumption that the period element candidates were exchanged with each other in respect to the locations or positions thereof at step 24. Subsequently, at step 25, a decision is made whether any cost improvement could be achieved. If it is decided that the cost for the paired element candidates will be able to be improved, e.g. when a difference resulting from subtraction of the pre-exchange cost (i.e. the cost involved unless the exchange is not performed) from the post-exchange cost has a sign of minus (negative), the processing proceeds to step 26. At step 26, the paired elements are exchanged in respect to the locations thereof, whereupon processing reutrns to step 23. On the other hand, if it is decided at step 25 that no improvement can be achieved in the cost, the processing proceeds to step 27 where the content of a counter C is incremented by "1", which is followed by step 28 at which a decision is made whether the content of the counter C is greater than the number N set at step 21. When this decision in step 28 results in C being smaller than N, processing returns to step 23 whereupon the processing succeeding thereto is repeated in the manner described above. Otherwise, i.e. when C is greater than N, the placement improving processing described above is terminated, and the information about the improved element placement is outputted at step 29. Thus, the processing comes to an end.
In conjunction with the related art element placement improving method outlined above, reference may be made to JP-A-62-93760 (Japanese Patent Application Laid-Open No. 93670/1987) and JP-A-62-243071.
The related art placement optimizing methods mentioned above have been developed for the integrated circuits having a relatively small number of the constituent elements. Accordingly, when the method is applied to a LSI having a high integration density as in the case of modern LSIs, the number N of the repetition times is remarkably increased, giving rise to a problem that an enormous amount of time is taken for the computation. Notwithstanding such high expenditure accompanying the conventional technology method, it is still difficult to determine the optimal element placement. This in turn presents a problem in deciding whether a further improvement of the element placement is possible.
Of the problems mentioned above, that of the time taken for the computation may be solved by using a parallel processing type computer system. In this computer system paired candidates are allocated to a plurality of CPUs for allowing them to compute the cost improvements, respectively, as is disclosed in, for example, JP-A-62-219062 and JP-A-62-175869. In particular, JP-A-62-17589 discloses a processing system for deciding module placement in which each of the locations or blocks for the elements is assigned with a CPU, wherein each CPU determines destinations to which the associated elements are to be moved with the aid of a procedure referred to as a gravity fgrce directed relaxation method. The names of the element is then sent by messsage to the CPUs belonging to the destinations. However, in this method, it is still difficult to realize the optimal placement for the reasons mentioned previously.
Another method for realizing the optimal element placement involves a simulated annealing method in which those candidates for which the positional exchange brings about deterioration rather than the improvement are determined. In this conjunction, reference may be made to "Technical Research Report VOD88-6 of the The Institute of Electronic Information and Communication Engineers of Japan", pp. 4-48. It is reported that by adopting this simulated annealing method, there can be realized the placement approximating to the optimum. However, this method also suffers from a problem that an enormous amount of time is taken for the computation. As an attempt for solving this problem, JP-A-63-121978 has proposed a system in which the abovementioned multi-processor method is adopted for determining stochastically whether or not the individual CPUs should perform the position exchanges in accordance with the simulated annealing method.
According to the related art methods in which the multi-processor system is adopted, reduction in the time required for the computation is attempted simply by allocating the tasks to a plurality of CPUs, wherein the results of the computations performed by the CPUs are taken into account independently of one another. By way of example, assuming that the repetitive improvement method described hereinbefore in conjunction with FIG. 13 of the accompanying drawings is carried out with the aid of the multi-processor system, the positions of the paired elements, as selected, for which it has been determined through computation that the exchange brings about improvement in respect to the cost will all be changed. This means that a lot of time needs to be taken for converging the element placement to the optimum.